public class AVLTree {
    static class TreeNode{
        public int val;
        public int bf;
        public TreeNode left;
        public TreeNode right;
        public TreeNode parent;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public TreeNode root;

    public void insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
        }
        TreeNode cur = root;
        TreeNode parent = null;
        while(cur != null) {
            if(val > cur.val) {
                parent = cur;
                cur = cur.right;
            }else if(val < cur.val) {
                parent = cur;
                cur = cur.left;
            }
        }
        if(parent.val > val) {
            parent.left = node;
            cur = node;
            cur.parent = parent;
        }else{
            parent.right = node;
            cur = node;
            cur.parent = parent;
        }
        while(parent != null) {
            if(parent.left == cur) {
                parent.bf--;
            }else{
                parent.bf++;
            }

            if(parent.bf == 0) {
                break;
            }else if(parent.bf == 1 || parent.bf == -1) {
                cur = parent;
                parent = parent.parent;
            }else{
                if(parent.bf == 2) {
                    if(cur.bf == 1) {
                        rotateL(parent);
                    }else {
                        //cur.bf == -1
                        rotateRL(parent);
                    }
                }else{
                    //parent.bf == -2
                    if(cur.bf == -1) {
                        rotateR(parent);
                    }else{
                        //cur.bf == 1;
                        rotateLR(parent);
                    }
                }
            }
        }
    }
    public void rotateR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        parent.left = subLR;
        if(subLR != null) {
            subLR.parent = parent;
        }
        TreeNode pParent = parent.parent;
        parent.parent =subL;
        subL.right=parent;
        if(parent == root) {
            root = subL;
            subL.parent = null;
        }else {
            if (pParent.left == parent) {
                pParent.left = subL;
            } else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = 0;
        parent.bf = 0;
    }

    public void rotateL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        TreeNode pParent = parent.parent;
        parent.right = subRL;
        if(subRL!=null) {
            subRL.parent = parent;
        }
        subR.left = parent;
        parent.parent = subR;
        if(parent == root) {
            root = subR;
            subR.parent = null;
        }else {
            if (pParent.left == parent) {
                pParent.left = subR;
            } else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        subR.bf = 0;
        parent.bf = 0;
    }
    public void rotateLR(TreeNode parent) {
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        rotateL(parent.left);
        rotateR(parent);
        int bf =subLR.bf;
        if(bf == -1) {
            subLR.bf = 0;
            subL.bf = 0;
            parent.bf = 1;
        }else if(bf == 1) {
            subLR.bf = 0;
            subL.bf = -1;
            parent.bf = 0;
        }
    }
    public void rotateRL(TreeNode parent) {
        TreeNode subR = parent.right;
        TreeNode subRL = subR.right;
        int bf = subRL.bf;
        rotateR(parent.right);
        rotateL(parent);
        if(bf == -1) {
            subR.bf = 1;
            subRL.bf = 0;
            parent.bf = 0;
        }else if(bf == 1){
            subR.bf = 0;
            subRL.bf = 0;
            parent.bf = -1;
        }
    }

    private int getHight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftH = getHight(root.left);
        int right = getHight(root.right);
        return leftH > right ? leftH+1:right+1;
    }

    public boolean isBalance(TreeNode root) {
        if(root == null) return true;
        int leftH = getHight(root.left);
        int rightH = getHight(root.right);

        if(rightH - leftH != root.bf) {
            System.out.println(root.val+" 平衡因子错误");
            return false;
        }
        return Math.abs(leftH-rightH) <=1
                && isBalance(root.left)
                && isBalance(root.right);
    }
}
